// 题目描述
// 124. 二叉树中的最大路径和
// 难度
// 困难
// 2001
// 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
// 路径和 是路径中各节点值的总和。
// 给你一个二叉树的根节点 root ，返回其 最大路径和 。
//   示例 1：
// 输入：root = [1,2,3]
// 输出：6
// 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
// 示例 2：
// 输入：root = [-10,9,20,null,null,15,7]
// 输出：42
// 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
//   提示：
// 树中节点数目范围是 [1, 3 * 104]
// -1000 <= Node.val <= 1000
// 通过次数329,711提交次数728,038

function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val)
  this.left = (left === undefined ? null : left)
  this.right = (right === undefined ? null : right)
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
  let ans = roo.val

  // root 为根的树上路径能提供的最大分数
  const helper = (root) => {
    if (!root) {
      return 0
    }

    const l = Math.max(0, helper(root.left))
    const r = Math.max(0, helper(root.right))

    // 同时可以统计以 root 为根包含左右子树路径的最大分数
    // 通过计算该分数更新全局最大分数也就是答案
    ans = Math.max(ans, root.val + l + r)

    return root.val + Math.max(l, r)
  }
  helper(root)

  return ans
}








